package com.example.leetcode.DFS;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例:
 *
 * 输入:
 *
 *    1
 *  /   \
 * 2     3
 *  \
 *   5
 *
 * 输出: ["1->2->5", "1->3"]
 *
 * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Description TODO
 * @date 2021/6/3 17:02
 * @Author liuzhihui
 * @Version 1.0
 */
class Solution_10_257 {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);

        treeNode1.left = treeNode2;
        treeNode2.right = treeNode5;
        treeNode1.right = treeNode3;

//        List<String> strings = binaryTreePaths(treeNode1);
    }
    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root){
        // helper(root, "");
        dfs(root,"");
        return res;
    }
    // 普通方法
    public void helper(TreeNode root, String pre){
        pre = pre + String.valueOf(root.val);
        if (root.left == null && root.right == null){
            res.add(pre);
            return;
        }
        if (root.left != null){
            helper(root.left, pre + "->");
        }
        if (root.right != null){
            helper(root.right, pre + "->");
        }
    }
    // 回溯法
    private void dfs(TreeNode root,String path) {
        path = path + String.valueOf(root.val);
        if (root.left == null && root.right == null){
            res.add(path);
            return;
        }
        if (root.left !=null){
            String temp =path;
            dfs(root.left,path + "->");
            // 回溯
            path = temp;
            // 想了想，回溯这个动作，好像是多余的
            // 如果左子树找完了，递归回到这个方法时，path还是之前的那个path,然后基于这个path，往下执行
            // 去右子树中找其他路径
        }
        if (root.right != null){
            dfs(root.right,path + "->");
        }
    }
}

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}